package cn.zhangchg.leetcode.arrays;


import java.util.*;

public class FindNumList {

    static Set<String> computeCourseSet;

    public static void main(String[] args) {
        Integer[] numbs = {97, 93, 54, 67, 10, 81, 33, 38, 68, 11, 17, 3, 10, 50, 23, 47, 25, 24, 4, 72, 72, 14, 61, 12, 39, 5, 51, 87, 60, 90, 90, 46, 26, 36, 88, 34, 19, 57, 94, 66, 20, 3, 13, 85, 37, 12, 6, 53, 92, 11, 75, 20, 6, 29, 58, 86, 53, 26, 20, 7, 44, 92, 77, 18, 33, 57, 42, 67, 85, 23, 79, 97, 51, 64, 80, 31, 31, 52, 75, 77, 95, 74, 32, 73, 13, 13, 89, 37, 49, 80, 42, 58, 34, 10, 12, 76, 18, 29, 13, 94, 42};
        Scanner input = new Scanner(System.in);

        while (true) {
            System.out.print("输入 start 开始游戏！其他内容将退出！");
            String command = input.next();
            if (!command.equalsIgnoreCase("START")) {
                break;
            }
            System.out.print("请输出想要得到的数字：");
            int target = input.nextInt();
            computeCourseSet = new HashSet<>();
            long startTime = System.currentTimeMillis();
            Set<List<Integer>> numList = findNumList(numbs, target);
            System.out.println("本次计算共花费：" + (System.currentTimeMillis() - startTime) + "毫秒");
            System.out.println("计算过程：");
            computeCourseSet.forEach(System.out::println);
            System.out.println("最终结果：");
            numList.forEach(System.out::println);
            System.out.println("共：" + numList.size() + "种结果");
        }
    }

    /**
     * 查询符合要求的数字列表
     *
     * @param numbs  原始数组
     * @param target 目标数字
     * @return 符合要求的数字数组集合
     */
    public static Set<List<Integer>> findNumList(Integer[] numbs, int target) {
        Set<List<Integer>> result = new HashSet<>();
        for (int i = 0; i < numbs.length; i++) {
            int indexStartAdd = computeIndex(numbs, target, i, 0, "");
            numbs[i] = -numbs[i];
            int indexStartSubtraction = computeIndex(numbs, target, i, 0, "");
            numbs[i] = -numbs[i];
            if (indexStartAdd != -1) {
                result.add(Arrays.asList(numbs).subList(i, indexStartAdd + 1));
            }
            if (indexStartSubtraction != -1) {
                result.add(Arrays.asList(numbs).subList(i, indexStartSubtraction + 1));
            }
        }
        return result;
    }

    /**
     * 计算符合数组的下标值
     *
     * @param numbs         原生数组
     * @param target        目标数字
     * @param index         数组下标
     * @param total         计算过程中的值
     * @param computeCourse 计算过程
     * @return 符合要求的数组的下标的值
     */
    private static int computeIndex(Integer[] numbs, int target, int index, int total, String computeCourse) {
        if (index + 1 > numbs.length) {
            return -1;
        }
        int temp = total;
        temp += numbs[index];

        if (temp > target) {
            total -= numbs[index];
            computeCourse += "-" + numbs[index];
        } else {
            total += numbs[index];
            computeCourse += "+" + numbs[index];

        }
        if (total == target) {
            if (computeCourse.startsWith("+-")) {
                computeCourse = computeCourse.replaceAll("\\+-", "-");
            }
            if (computeCourse.startsWith("--")) {
                computeCourse = computeCourse.replaceAll("--", "+");
            }
            computeCourseSet.add(computeCourse);
            return index;
        }
        index++;
        return computeIndex(numbs, target, index, total, computeCourse);
    }

}